/** \file    MergeByColor.cpp
  * \brief   Merge segments to reduce dispersion of color in them and eliminate small segments.
  * \date    2002
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/segm/src/MergeByColor.cpp,v 1.1 2004/05/20 09:11:46 cscom1r4 Exp $
  */

#include "segm/MergeSegmentation.h"
#include "imglib/segmcomb.h"

struct dispersion_patch: public img::merge_patch<>
{
	float_color m;
	float d;

	dispersion_patch() 
		{}
	dispersion_patch(const Segment &g) 
		{ pixels = g.pixelCount; 
		  m = g.meanColor;
		  d = g.colorDispersion; }

	static dispersion_patch merge(dispersion_patch p1, const dispersion_patch &p2) {
		size_t pixels = p1.pixels + p2.pixels;
		float r1 = float(p1.pixels) / pixels;
		float r2 = float(p2.pixels) / pixels;
		float_color m = p1.m*r1 + p2.m*r2;
		float d = r1*p1.d + r2*p2.d + r1*r2*square(p1.m-p2.m);

		p1.pixels = pixels;
		p1.m = m;
		p1.d = d;
		return p1;
	}

	void subdue(dispersion_patch &child) {
		*this = merge(*this, child);
	}
};

typedef std::vector<dispersion_patch> dispersion_arr;

///\return win in dispersion
static float bestNei(const Segmentation &s, dispersion_arr &arr, int x, int &nei_idx)
{
	nei_idx = -1;
	const dispersion_patch &p = arr[x];
	if (!p.is_root())
		return 0;

	const Segment &g = s.segmentByIndex(x);

	IntIntMap::const_iterator i;
	float delta = FLT_MAX;
	for (i = g.neighbours.begin(); i != g.neighbours.end(); ++i) {
		int x2 = xtd::find_root_idx(arr, i->second);
		if (x == x2)
			continue;
		dispersion_patch mrg = dispersion_patch::merge(p, arr[x2]);
		float d = mrg.d - p.d;
		if (d < delta) {
			delta = d;
			nei_idx = x2;
		}
	}

	return delta;
}

void Segmentation::mergeByColor(size_t enough_pixels, bool merge_large)
{
	colorStatistics();
	dispersion_arr arr(count());
	std::copy(segmentsBegin(), segmentsEnd(), arr.begin());

	//repeat while dispersion can't be lowered in any segment
	bool f;
	for (;merge_large;) {
		f = false;
		int i, nei_idx;
		for (i = 0; i != count(); ++i) {
			if (0 > bestNei(*this, arr, i, nei_idx) && nei_idx != -1) {
				f = true;
				arr[i].merge_with = nei_idx;
			} else {
				arr[i].merge_with = dispersion_patch::no_parent_value();
			}
		}
		if (!f)
			break;
		img::do_merge_with(arr);
	}

	//repeat while where will be no small segments
	for (;;) {
		f = false;
		int i, nei_idx;
		for (i = 0; i != count(); ++i) {
			if (xtd::find_root(arr, i).pixels < enough_pixels && 
				(bestNei(*this, arr, i, nei_idx), nei_idx != -1)) 
			{
				f = true;
				arr[i].merge_with = nei_idx;
			} else {
				arr[i].merge_with = dispersion_patch::no_parent_value();
			}
		}
		if (!f)
			break;
		img::do_merge_with(arr, enough_pixels);
	}

	merge(arr);
}

